package hl.leco;

import hl.leco.colle.tree.TreeNode;

import java.text.DecimalFormat;
import java.util.*;

/**
 * 
 * @author Liu Huan
 */


class Solution {
	public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
		List<List<Integer>> list = new LinkedList<>();
		helper(root, list);
		return list;
	}
	
	public void helper(TreeNode root, List<List<Integer>> list){
		//辅助栈，存放每层的节点
		Stack<TreeNode> stack = new Stack<>();
		if(root!=null){
			stack.push(root);
		} else {
			return;
		}
		
		boolean flag = true;
		while(!stack.isEmpty()){
			
			//每层 定义一个临时 list,添加当前层的节点
			List<Integer> templist = new LinkedList<>();
			
			int len = stack.size();
			//System.out.print(len);
			for(int i=0; i<len; i++){
				//获取元素，访问，添加左右子树
				TreeNode node = stack.pop();
				templist.add(node.val);
				if(flag){
					if(node.left!=null)     stack.push(node.left);
					if(node.right!=null)    stack.push(node.right);
				} else {
					if(node.right!=null)    stack.push(node.right);
					if(node.left!=null)     stack.push(node.left);
				}
				
			}
			
			//将临时list 添加到 最终的list
			list.add(templist);
			flag = !flag;
		}
		
	}
	
	public static void main(String[] args) {
		DecimalFormat df   = new DecimalFormat("0.00");
		double d1 = 3.234;
		double d2 = 3.2351;
		double d3 = 3.237;
		System.out.println(df.format(d1));
		System.out.println(df.format(d2));
		System.out.println(df.format(d3));
	}
}